#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
/*
给定一个包含不重复整数的数组 arr，以及一个整数 targetNum
在 arr 中找出所有三个数字的组合，让他们的和是 targetSum。

arr = [12, 3, 1, 2, -6, 5, -8, 6]
targetNum = 0

{
  {-8, 2, 6},
  {-8, 3, 5},
  {-6, 1, 5}
}
*/

/*
targetNum = 0
-8, -6, 1, 2, 3, 5, 6, 12
        ^i    ^l ^r
    -6 + 12 = 6 < 8
    1  + 12 = 13 > 8
    1 + 6   = 7 < 8
    2 + 6   = 8
    ......
    l >= r
*/

vector<vector<int>> threeNumSum(vector<int> &arr, int targetNum) {
  sort(arr.begin(), arr.end());
  vector<vector<int>> result;

  for (int i = 0; i < arr.size(); ++i) {
    if (arr[i] >= targetNum) {
      break;
    }

    int l = i + 1;
    int r = arr.size() - 1;

    // 我们要在 l 和 r 之间找谁？
    int n = targetNum - arr[i];

    while (l < r) {
      int m = arr[l] + arr[r];

      if (m == n) {
        result.push_back({arr[i], arr[l], arr[r]});
        l += 1;
        r -= 1;
      }
      else if (m > n) {
        r -= 1;
      }
      else {
        // m < n
        l += 1;
      }
    }
  }

  return result;
}

int main(int argc, char const *argv[])
{
  /* code */
  return 0;
}
